#include<stdio.h>
#include<stdlib.h>
typedef struct ListNode {
    int val;
    struct ListNode* next;
}ListNode;
ListNode* partition(ListNode* head, int x) 
{
    ListNode* smallHead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* bigHead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* small = smallHead;
    ListNode* big = bigHead;
    while (head != NULL)
    {
        if (head->val < x)
        {
            small->next = head;
            small = small->next;
        }
        else
        {
            big->next = head;
            big = big->next;
        }
        head = head->next;
    }
    big->next = NULL;
    small->next = bigHead->next;
    return smallHead->next;
}
void test()
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h3 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h4 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h5 = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;
    h1->val = 4;
    h2->val = 3;
    h3->val = 2;
    h4->val = 5;
    h5->val = 2;
    head->next = h1;
    h1->next = h2;
    h2->next = h3;
    h3->next = h4;
    h4->next = h5;
    h5->next = NULL;
    ListNode* ret = partition(head, 3);
    while (ret != NULL)
    {
        printf("%d->", ret->val);
        ret = ret->next;
    }
    printf("NULL\n");
}
int main()
{
    test();
	return 0;
}